OcrV1, Main, Exploration, bibRecord, 000A96

A quadratic time 2-approximation algorithm for block sorting

Identifieur interne : 000A96 ( Main/Exploration ); précédent : 000A95; suivant : 000A97

A quadratic time 2-approximation algorithm for block sorting

Auteurs : Wolfgang W. Bein [États-Unis] ; Lawrence L. Larmore [États-Unis] ; Linda Morales [États-Unis] ; I. Hal Sudborough [États-Unis]

Source :

Theoretical computer science [ 0304-3975 ] ; 2009.

RBID : Pascal:09-0158458

Descripteurs français

Pascal (Inist)
- Approximation quadratique, Algorithme approximation, Triage, Concept, Délétion, Optimum, Raccordement, Reconnaissance caractère, Transposition, Biologie, Conception, Analyse algorithme, Informatique théorique, 68W25, 68Wxx, 68P10, 05Bxx, 68Q25, 68W40.
Wicri :
- topic : Biologie.

English descriptors

KwdEn :
- Algorithm analysis, Approximation algorithm, Biology, Character recognition, Computer theory, Concept, Connection, Deletion, Design, Optimum, Quadratic approximation, Sorting, Transposition.

Abstract

The block sorting problem is the problem of minimizing the number of steps to sort a list of distinct items, where a sublist of items which are already in sorted order, called a block, can be moved in one step. We give an approximation algorithm for the block sorting problem with an approximation ratio of 2 and run time O(n²). The approximation algorithm is based on the related concept of block deletion. We show that finding an optimum block deletion sequence can be done in O(n²) time, even though block sorting is known to be N P-hard. Block sorting has importance in connection with optical character recognition (OCR) and is related to transposition sorting in computational biology.

Affiliations:

États-Unis
Nevada, Texas

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: 000233
to stream PascalFrancis, to step Curation: 000546
to stream PascalFrancis, to step Checkpoint: 000213
to stream Main, to step Merge: 000B07
to stream Main, to step Curation: 000A96

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">A quadratic time 2-approximation algorithm for block sorting</title>
<author><name sortKey="Bein, Wolfgang W" sort="Bein, Wolfgang W" uniqKey="Bein W" first="Wolfgang W." last="Bein">Wolfgang W. Bein</name>
<affiliation wicri:level="2"><inist:fA14 i1="01"><s1>Center for the Advanced Study of Algorithms, School of Computer Science, University of Nevada</s1>
<s2>Las Vegas, NV 89154</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<placeName><region type="state">Nevada</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Larmore, Lawrence L" sort="Larmore, Lawrence L" uniqKey="Larmore L" first="Lawrence L." last="Larmore">Lawrence L. Larmore</name>
<affiliation wicri:level="2"><inist:fA14 i1="01"><s1>Center for the Advanced Study of Algorithms, School of Computer Science, University of Nevada</s1>
<s2>Las Vegas, NV 89154</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<placeName><region type="state">Nevada</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Morales, Linda" sort="Morales, Linda" uniqKey="Morales L" first="Linda" last="Morales">Linda Morales</name>
<affiliation wicri:level="2"><inist:fA14 i1="02"><s1>Department of Computer Science, University of Texas</s1>
<s2>Dallas Richardson, TX 75083</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<placeName><region type="state">Texas</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Hal Sudborough, I" sort="Hal Sudborough, I" uniqKey="Hal Sudborough I" first="I." last="Hal Sudborough">I. Hal Sudborough</name>
<affiliation wicri:level="2"><inist:fA14 i1="02"><s1>Department of Computer Science, University of Texas</s1>
<s2>Dallas Richardson, TX 75083</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<placeName><region type="state">Texas</region>
</placeName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">09-0158458</idno>
<date when="2009">2009</date>
<idno type="stanalyst">PASCAL 09-0158458 INIST</idno>
<idno type="RBID">Pascal:09-0158458</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000233</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000546</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000213</idno>
<idno type="wicri:doubleKey">0304-3975:2009:Bein W:a:quadratic:time</idno>
<idno type="wicri:Area/Main/Merge">000B07</idno>
<idno type="wicri:Area/Main/Curation">000A96</idno>
<idno type="wicri:Area/Main/Exploration">000A96</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">A quadratic time 2-approximation algorithm for block sorting</title>
<author><name sortKey="Bein, Wolfgang W" sort="Bein, Wolfgang W" uniqKey="Bein W" first="Wolfgang W." last="Bein">Wolfgang W. Bein</name>
<affiliation wicri:level="2"><inist:fA14 i1="01"><s1>Center for the Advanced Study of Algorithms, School of Computer Science, University of Nevada</s1>
<s2>Las Vegas, NV 89154</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<placeName><region type="state">Nevada</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Larmore, Lawrence L" sort="Larmore, Lawrence L" uniqKey="Larmore L" first="Lawrence L." last="Larmore">Lawrence L. Larmore</name>
<affiliation wicri:level="2"><inist:fA14 i1="01"><s1>Center for the Advanced Study of Algorithms, School of Computer Science, University of Nevada</s1>
<s2>Las Vegas, NV 89154</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<placeName><region type="state">Nevada</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Morales, Linda" sort="Morales, Linda" uniqKey="Morales L" first="Linda" last="Morales">Linda Morales</name>
<affiliation wicri:level="2"><inist:fA14 i1="02"><s1>Department of Computer Science, University of Texas</s1>
<s2>Dallas Richardson, TX 75083</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<placeName><region type="state">Texas</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Hal Sudborough, I" sort="Hal Sudborough, I" uniqKey="Hal Sudborough I" first="I." last="Hal Sudborough">I. Hal Sudborough</name>
<affiliation wicri:level="2"><inist:fA14 i1="02"><s1>Department of Computer Science, University of Texas</s1>
<s2>Dallas Richardson, TX 75083</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<placeName><region type="state">Texas</region>
</placeName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
<imprint><date when="2009">2009</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm analysis</term>
<term>Approximation algorithm</term>
<term>Biology</term>
<term>Character recognition</term>
<term>Computer theory</term>
<term>Concept</term>
<term>Connection</term>
<term>Deletion</term>
<term>Design</term>
<term>Optimum</term>
<term>Quadratic approximation</term>
<term>Sorting</term>
<term>Transposition</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Approximation quadratique</term>
<term>Algorithme approximation</term>
<term>Triage</term>
<term>Concept</term>
<term>Délétion</term>
<term>Optimum</term>
<term>Raccordement</term>
<term>Reconnaissance caractère</term>
<term>Transposition</term>
<term>Biologie</term>
<term>Conception</term>
<term>Analyse algorithme</term>
<term>Informatique théorique</term>
<term>68W25</term>
<term>68Wxx</term>
<term>68P10</term>
<term>05Bxx</term>
<term>68Q25</term>
<term>68W40</term>
</keywords>
<keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Biologie</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">The block sorting problem is the problem of minimizing the number of steps to sort a list of distinct items, where a sublist of items which are already in sorted order, called a block, can be moved in one step. We give an approximation algorithm for the block sorting problem with an approximation ratio of 2 and run time O(n<sup>2</sup>
). The approximation algorithm is based on the related concept of block deletion. We show that finding an optimum block deletion sequence can be done in O(n<sup>2</sup>
) time, even though block sorting is known to be N P-hard. Block sorting has importance in connection with optical character recognition (OCR) and is related to transposition sorting in computational biology.</div>
</front>
</TEI>
<affiliations><list><country><li>États-Unis</li>
</country>
<region><li>Nevada</li>
<li>Texas</li>
</region>
</list>
<tree><country name="États-Unis"><region name="Nevada"><name sortKey="Bein, Wolfgang W" sort="Bein, Wolfgang W" uniqKey="Bein W" first="Wolfgang W." last="Bein">Wolfgang W. Bein</name>
</region>
<name sortKey="Hal Sudborough, I" sort="Hal Sudborough, I" uniqKey="Hal Sudborough I" first="I." last="Hal Sudborough">I. Hal Sudborough</name>
<name sortKey="Larmore, Lawrence L" sort="Larmore, Lawrence L" uniqKey="Larmore L" first="Lawrence L." last="Larmore">Lawrence L. Larmore</name>
<name sortKey="Morales, Linda" sort="Morales, Linda" uniqKey="Morales L" first="Linda" last="Morales">Linda Morales</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000A96 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000A96 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Ticri/CIDE
   |area=    OcrV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Pascal:09-0158458
   |texte=   A quadratic time 2-approximation algorithm for block sorting
}}

This area was generated with Dilib version V0.6.32.
Data generation: Sat Nov 11 16:53:45 2017. Site generation: Mon Mar 11 23:15:16 2024

	Serveur d'exploration sur l'OCR
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur l'OCR

A quadratic time 2-approximation algorithm for block sorting

A quadratic time 2-approximation algorithm for block sorting

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri